package j2024.j202410;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class j1009 {
    /**
     * 141. 环形链表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     *
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
     * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
     * 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     *
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }

    /**
     * 289. 生命游戏
     * 根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
     *
     * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或
     * 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
     *
     * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
     * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
     * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
     * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
     * 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
     * 给你 m x n 网格面板 board 的当前状态，返回下一个状态。
     * @param board
     */
    int[] dy = new int[]{1,1,0,-1,-1,-1,0,1};
    int[] dx = new int[]{0,-1,-1,-1,0,1,1,1};
    public void gameOfLife(int[][] board) {
        int m = board.length,n = board[0].length;
        int[][] vis = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vis[i][j] = search(board,i,j);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j]==1){
                    if(vis[i][j]<2||vis[i][j]>3){
                        board[i][j]=0;
                    }
                }else{
                    if(vis[i][j]==3){
                        board[i][j]=1;
                    }
                }
            }
        }
    }
    public int search(int[][] b,int i,int j){
        int ret = 0;
        for (int k = 0; k < 8; k++) {
            int x = i+dx[k];
            int y = j+dy[k];
            if(x>=0 && x<b.length && y>=0 && y<b[0].length && b[x][y]==1){
                ret++;
            }
        }
        return ret;
    }
}
